class Solution
{
public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {
        int n = startTime.size();
        vector<int> jobId(n);
        iota(jobId.begin(), jobId.end(), 0);
        sort(jobId.begin(), jobId.end(), [&endTime](int l, int r)
             { return endTime[l] < endTime[r]; });
        vector<int> dp(n + 1);
        dp[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            auto lastEnd = upper_bound(jobId.begin(), jobId.begin() + i, jobId[i], [&](int startI, int endI)
                                       { return startTime[startI] < endTime[endI]; });
            int foreJobCount = lastEnd - jobId.begin();
            dp[i + 1] = max(dp[i], dp[foreJobCount] + profit[jobId[i]]);
        }
        return dp[n];
    }
};